# 递归 左右匹配的就去除
class Solution:
    def __init__(self):
        self.diat1 = {
            '(': ')',
            '[': ']',
            '{': '}'
        }

    # def isValid(self, s: str) -> bool:
    #     list1 = list(s)
    #     if len(list1) % 2 == 1:
    #         return False
    #     flag1 = -1
    #     if (list1[0] in self.diat1) == False:
    #         return False
    #     for i in range(len(list1)):
    #         if (list1[i] in self.diat1):
    #             flag1 += 1
    #         else:
    #             if (list1[i] == self.diat1[list1[flag1]]):
    #                 del list1[flag1:i + 1]
    #                 if (len(list1) == 0):
    #                     return True
    #                 else:
    #                     return self.isValid(''.join(list1))
    #             else:
    #                 return False
    #     if (flag1 == len(list1) - 1):
    #         return False

    def isValid(self, s: str) -> bool:
        list1=[]
        list2=list(s)
        for i in range(len(list2)):
            if(len(list1)==0):
                list1.append(list2[i])
                continue
            if( (list1[-1] in self.diat1)==True and self.diat1[list1[-1]]==list2[i]):
                list1.pop(-1)
            else:
                list1.append(list2[i])
        if(len(list1)==0):
            return True

        return False


lll = Solution()
print(lll.isValid('()'))
